/*Trabalho 2
 *Desenvolvido por 
 *Erick Becker-7152653
 *Marcelo Montanher- 
 *William Silva- 7152382
 */

#include <stdio.h>
#include <stdlib.h>
#include "grafo.h"
#include <mpi.h>

/*
Função que armazena as ruas do sistema num grafo
Entrada:-n_streets: 	numero total de ruas da cidade
        -vertc:		    matriz com o grafo
*/
int get_streets(int n_streets, float** graph){
	int i = 0;
	int vertA, vertB;
	float weight;

	for( i = 0; i < n_streets; i++){
		scanf("%d %d %f", &vertA, &vertB, &weight);
        graph_insert(graph, vertA-1, vertB-1, weight);
	}

	return 0;
}

/*
Analisa a matriz e retorna a maior distancia para o melhor vertice
*/
int find_best_vertex_distance(float **mat, int n_corners){
    float best_value=100000000;
    float aux;
    int i,j;

    for(i=0;i<n_corners;i++){
        aux=0;
        // verifica a linha
        for(j=0;j<n_corners;j++){
            if(mat[i][j]>aux){      // Pega o maior valor
                aux=mat[i][j];
            }
        }
        if(aux<best_value){
            best_value=aux;
        }
    }
    return best_value;
}


int main(){
	int n_streets;		// Numero total de ruas do sistema
    int n_corners;  	// Numero total de esquinas
    float **graph;		// Grafo
	float *vet_aux; 	// Vetor que será enviado para cada processo
    float *vet_k;		// Vetor k, para analise
    int numtasks, rank, size, dest, source, count, tag=1;
    int i;
	MPI_Status Stat;

    MPI_Init(NULL, NULL);

    MPI_Comm_rank(MPI_COMM_WORLD, &rank);
    MPI_Comm_size(MPI_COMM_WORLD, &size);
    if(rank==0){
    	// Leitura do numero de esquinas e ruas
        scanf("%d %d", &n_corners, &n_streets);


		// Envia o número de ruas para os filhos 
        for(i=1;i<size;i++){
            MPI_Send(&n_corners, 1, MPI_INT, i, tag, MPI_COMM_WORLD);
        }

        // Aloca espaço do grafo
        graph=graph_init(n_corners);

        // Leitura dos valores das ruas
        get_streets(n_streets, graph);

        // Inicia o algoritmo de F-W
        int k, j, counter, row;
		//printf("%d mod %d = %d\n",n_corners, size-1, n_corners%(size-1));
		
        for(k=0;k<n_corners;k++){
            counter=1;
            for(row=0; row<n_corners; row++){
                // Envia o valor de k
                MPI_Send(&k, 1, MPI_INT, counter, tag, MPI_COMM_WORLD);

                // Envia a coluna do k
                MPI_Send(graph[k], n_corners, MPI_FLOAT, counter, tag, MPI_COMM_WORLD);

                // Envia a coluna auxiliar
                MPI_Send(graph[row], n_corners, MPI_FLOAT, counter, tag, MPI_COMM_WORLD);

                counter++;
                if(counter==size){
                    for(j=1;j<size;j++){
                        // Começa a receber o resultado
                        MPI_Recv(graph[row-size+1+j], n_corners, MPI_FLOAT, j, tag, MPI_COMM_WORLD, &Stat);
                        // Atualiza a matriz
                    }
					counter=1;
                }
            }

            for(j=1;j<=n_corners%(size-1);j++){
                // Começa a receber o resultado
                MPI_Recv(graph[row-size+j+1], n_corners, MPI_FLOAT, j, tag, MPI_COMM_WORLD, &Stat);
                // Atualiza a matriz
            }
        }

        // Encerra os cara
        for(i=1;i<size;i++){
            k=-1;
            MPI_Send(&k, 1, MPI_INT, i, tag, MPI_COMM_WORLD);
        }

        // encontra a maxima distancia para o melhor lugar para o hospital
        printf("%d\n",find_best_vertex_distance(graph,n_corners));
		for(i=0; i<n_corners; i++){
			free(graph[i]);
		}
		free(graph);

    }else{

        source=0;

        // Recebe o numero de vértices
        MPI_Recv(&n_corners, 1, MPI_INT, source, tag, MPI_COMM_WORLD, &Stat);
        vet_aux=(float*)malloc(sizeof(float)*n_corners);
        vet_k=(float*)malloc(sizeof(float)*n_corners);

        int k;
        while(1){
            MPI_Recv(&k, 1, MPI_INT, source, tag, MPI_COMM_WORLD, &Stat);
            if(k==-1){
                break;  // Mensagem indicando fim da rotina
            }
            MPI_Recv(vet_k, n_corners, MPI_FLOAT, source, tag, MPI_COMM_WORLD, &Stat);
            MPI_Recv(vet_aux, n_corners, MPI_FLOAT, source, tag, MPI_COMM_WORLD, &Stat);

            for(i=0;i<n_corners;i++){
                if(vet_aux[k]+vet_k[i]<vet_aux[i]){
                    vet_aux[i]=vet_aux[k]+vet_k[i];
                }
            }
            MPI_Send(vet_aux, n_corners, MPI_FLOAT, source, tag, MPI_COMM_WORLD);
        }
		free(vet_aux);
     	free(vet_k);
	}
	MPI_Finalize();

	return 0;
}
